The present invention relates to an optimum route calculation method and optimum route calculation program which derive, with a small calculation amount, a route that is reachable with a small number of hops while avoiding any bottleneck portions in a communication network.
A conventional typical route calculation algorithm is the Dijkstra's algorithm which calculates the total costs of links in routes as evaluation values and selects a route with the minimum total cost. The Dijkstra's algorithm is widely used as a calculation method with the shortest route calculation time.
However, the Dijkstra's algorithm may select a route passing through a link that can be a traffic bottleneck in the network and has an excessively high cost. This is because since the total cost value is used as the evaluation value for routing, even the excessively high link cost may be canceled by synthesis.
An example of a system to solve this problem is disclosed in a route calculation method of Japanese patent Laid-Open No. 2001-244974. This prior art is a connectionless communication network constituted by terminal apparatuses, repeaters, and a plurality of links that connect the apparatuses. According to the characteristic feature of this connectionless communication network, when a routing parameter (cost) is assigned to each link, and a route from an arbitrary terminal apparatus to another arbitrary terminal apparatus in the communication network is to be calculated, one of the plurality of routes that connect the terminal apparatuses, whose minimum cost of each link included in the route is maximum, is calculated.
In the route calculation method disclosed in Japanese patent Laid-Open No. 2001-244974 described above, however, although a link that may be a bottleneck can be avoided, a route having an excessively large number of hops may be selected because the costs are not added. In a network, an increase in the number of hops may lead to an increase in transfer delay or the like.